1. Field of the Invention
The present invention relates to a memory access method and system in a computer system constructed of a plurality of processors or a plurality of processor equivalent circuits.
2. Description of the Prior Art
When a multiprocessor system having a shared memory or a parallel processing system executes a series of data processes, interruption of other data processing operations during the former data processing in some cases causes problems. A synchronous operation may also be required, wherein the respective processors process the data assigned thereto, and total processing is effected after the processed results thereof have all been obtained.
For this reason, a multiprocessor system having a shared memory needs an "atomic" memory access function. This function performs an exclusive operation which does not permit memory accessing from other programs during a reading sequence or writing a series of data with respect to the data processing in a shared memory region.
Operations such as reading from and writing into the memory are herein referred to as a memory access. A memory access sequence in which a series of operations are undividable by other programs or processors is called an "atomic" memory access.
This atomic memory access function has hitherto been attainable by a read-modify-write function of the memory in a special case where the write operation is effected subsequently to the read operation.
As reported in, e.g., "Interprocess Communication Mechanisms", Paragraph 8.1, of "Computer Architecture and Parallel Processing" written by K. Hwang & F. A. Briggs (McGraw-Hill Book Company, 1984), that is a well-known technique.
The read-modify-write function of the memory is a function by which the data is read from a specified address at each of continuous memory cycles, the data is subsequently written to the same address, and meanwhile a memory reference from other addresses is inhibited. These functional operations of the memory are attainable by utilizing a read-modify-write function incorporated into 256KB DRAM CHIP MSM4256 proposed in, e.g., ['88 Mitsubishi Semiconductor Data Book: Memory] edited by Mitsubishi Electric Co., Ltd.
When actualizing the atomic memory access function by use of the read-modify-write function, it is required that a memory bus be dedicatedly used to enable a processor to execute the read-modify-write operation to exclusively effect the memory access. In this manner, the atomic memory access can be fulfilled by inhibiting the interruption and execution of memory accessing by other processors.
This kind of hardware operation will now be discussed in terms of a program or micro machine instruction.
As stated in "Synchronization, Coherence, and Event Ordering in Multiprocessors" (IEEE Computer, Vol. 21, No. 2, February 1988, pp. 9-21) written by F. A. Briggs, the machine instruction includes a Test & Set instruction and/or a Compare & Swap instruction. Both of them are instructions to exclusively access a region in the memory.
The Test & Set instruction exclusively executes the following operation as an inseparable one:
Test & Set (x) PA1 {temp.rarw.x; x.rarw.1; return temp;} PA1 Compare & Swap (r1, r2, w) PA1 {temp.rarw.w; if (temp=r1) PA1 then {w.rarw.r2; z.rarw.1} PA1 else {r1.rarw.temp; z.rarw.0}}
On the other hand, the Compare & Swap instruction exclusively executes the following operation as an inseparable one:
where z is the flag variable. z is set to 0 or 1 in accordance with the comparative results.
A set of these instructions are employed for securing and releasing the occupation by use of a lock variable provided corresponding to an inter-program shared resource. For instance, the lock is set to such a lock variable. If lock=0, it is assumed that a resource R corresponding to the lock is not secured from any program. If lock=1, the assumption is that the resource R is secured in any one of programs. When a certain program P now secures the resource R, the following operation is at first carried out. EQU y=Test & Set (lock)
A previous value of the lock is stored in the variable y. Hence, an examination of this makes it possible to know whether the lock value is 0 or 1 before the execution of the Test & Set instruction. If the value is 0, it implies that the corresponding resource R is free, and then lock=1 by the Test & Set instruction. It follows that an authorization of use about the resource R is obtained in a program P. If y is 1, the resource R is secured by a program other than P. The program P repeats the Test & Set instruction till the resource R is released.
The operations discussed above have been explained in association with the Test & Set instruction. The compare & Swap instruction is usable for the same operations.
The Test & Set instruction is, as described above, employed for securing the occupation by handling the lock variable corresponding to the resource. In general, there is no special instruction to release the lock variable to make the resource open after the use of resource has been terminated. Based on the example given above, lock.rarw.0, i.e., 0 may simply be stored in the lock, and hence an ordinary store instruction is used.
The operation is the same with the Compare & Swap instruction.
Note that in the Test & Set instruction and the Compare & Swap instruction which are employed for the atomic memory access, data read and data write subsequent thereto are performed as a series of exclusive operations, and in the meantime other memory accesses are not permissible.
The read-modify-write function has been employed to effect the atomic memory access in the prior art multiprocessor system. When one processor performs the read-modify-write function, a memory bus for connecting the processor to the memory is occupied. Other processors have to wait till the atomic memory access is finished even in the case of a memory access to a region different from an object region of the atomic memory access. As a result, the processing time is delayed. This is the first problem.
In the prior art, the atomic memory access is feasible with respect to only the read and the write subsequent thereto. The atomic access can not be done during an arbitrary read/write sequence.
Disclosed in Japanese Patent Laid-Open No. 59-116866 is a technique by which the atomic memory access is managed per address, and the memory access to a different memory region can be executed.
Considering that the atomic memory access is also required for a synchronous operation between the multiple processors, however, it is insufficient to simply permit the memory accesses to the different regions from a plurality of processors. Namely, there exists a possibility of a data destruction or system runaway unless an appropriate execution of the memory access per process or program is assured.
The following is a description of the second problem. In the case of a machine instruction architecture, the conventional Test & Set instruction and/or the Compare & Swap instruction are available for starting the atomic memory access. No special instruction is, however, provided for terminating the atomic memory access. Instead, an ordinary Store instruction or an instruction corresponding thereto is employed. Under such circumstances, the former is confused with other data Store instructions. This in turn induces a mistake in programming.
The third problem will hereinafter be explained. The conventional systems did not presume parallel accessing of the memory. Therefore, the Test & Set instruction and the Compare & Swap instruction merely protect a series of operations, viz., the object memory regions at that time. The management for correctness of a subsequent program or other programs simultaneously executed was not taken into consideration. Consequently, there is a possibility that the data or system may be destroyed by an incorrect program. Reliability is thereby caused to deteriorate.
Coping with the first through third problems, this invention aims at reducing time for the complete memory accesses while assuring the conventionally unconsidered correctness of the program or of the system operation.